2016. Перепродажа билетов

 

Вам известно, что в кассе кинотеатра имеется n билетов. Также известно, сколько Вам придется заплатить за каждый билет, если вы решите его купить (стоимость покупки), и за какую сумму вы сможете его потом перепродать (стоимость продажи). Изначально у Вас есть 1 гривна, вы можете купить какие-то из n билетов (возможно все) и затем перепродать их. Покупка и перепродажа осуществляются в произвольном порядке. Необходимо определить, какую максимальную сумму вы получите в итоге.

 

Вход. В первой строке дано количество билетов n (1 ≤ n ≤ 105). Далее идут n строк, в каждой из которых записаны по два целых числа bi и si (1 ≤ bi, si ≤ 109) – стоимости покупки и продажи i-го билета в гривнах.

 

Выход. Вывести максимальную сумму, которая получится в итоге.

 

Пример входа

Пример выхода

6

4 4

1 2

2 5

7 10

6 2

3 4

6

 

 

РЕШЕНИЕ

жадность

 

Анализ алгоритма

Билет представляем парой (b, s) = (стоимость покупки, стоимость продажи). Билеты, для которых b ≥ s, нас не интересуют – с них невозможно получить прибыль. Остальные билеты отсортируем по возрастанию стоимости покупки.

Изначально у Вас имеется sum = 1 гривна. Перебираем билеты. Если стоимость покупки очередного билета больше имеющегося у Вас количества денег sum, то завершаем алгоритм и выводим ответ sum. Иначе получаем прибыль с покупки / продажи текущего билета (b, s), увеличив sum на s – b.

 

Пример

Билеты из заданного примера будут отсортированы следующим образом (рассматриваются только те билеты, для которых b < s).

После обработки трех билетов получится сумма, равная 6. Купить билет (7, 10) невозможно, так как имеющаяся в наличии сумма в 6 гривен меньше его стоимости покупки.

 

Реализация алгоритма

Билеты представляем парами (b, s) и храним в массиве v.

 

vector<pair<int, int> > v;

 

Читаем входные данные. Заносим в массив v билеты, для которых b < s.

 

scanf("%d", &n);

for (i = 0; i < n; i++)

{

  scanf("%d %d", &b, &s);

  if (b < s) v.push_back(make_pair(b, s));

}

 

Сортируем билеты по возрастанию стоимости покупки.

 

sort(v.begin(), v.end());

 

Изначально у Вас имеется sum = 1 гривна.

 

sum = 1;

 

Перебираем билеты по возрастанию стоимости покупки. Если стоимость покупки очередного билета v[i].first больше имеющегося у Вас количества денег sum, то завершаем цикл for. Иначе увеличиваем sum на прибыль, полученную от купли / продажи i-го билета.

 

for (i = 0; i < v.size(); i++)

  if (v[i].first <= sum) sum += v[i].second - v[i].first;

  else break;

 

Выводим ответ.

 

printf("%lld\n", sum);